This leads us to the Shortest Path Problem, which seeks the route with the minimum total cost.

  • The Shortest Path Problem is defined on a weighted graph $G = (V, E)$.
  • Goal: Find the path $P$ from a source $s$ to a target $t$ such that the total cost, $\sum w(u, v)$, is minimized.
  • The cost of any other path $P'$ must satisfy $Cost(P) \le Cost(P')$.
  • A common variation is the Single-Source Shortest Path problem, finding the shortest path from $s$ to all other vertices $v$.
  • Algorithms like Dijkstra's solve this variation, resulting in a set of minimum distances, $d[v]$.
Formal Definition: Shortest Path Cost
1# The minimum cost from source s to target t
2
3def shortest_path_cost(s, t):
4    # d(s, t) = min { Cost(P) | P is a path from s to t }
5    if path_exists(s, t):
6        return min(cost(P) for P in all_paths(s, t))
7    else:
8        return Infinity  # $\infty$